home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / ThreadEventPairingHeap.h,v < prev    next >
Text File  |  1988-10-12  |  6KB  |  237 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @ * @;
  6.  
  7.  
  8. 1.1
  9. date     88.10.12.10.51.13;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @// This may look like C code, but it is really -*- C++ -*-
  25. /* 
  26. Copyright (C) 1988 Free Software Foundation
  27.     written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  28.     adapted for libg++ by Doug Lea (dl@@rocky.oswego.edu)
  29.  
  30. This file is part of GNU CC.
  31.  
  32. GNU CC is distributed in the hope that it will be useful,
  33. but WITHOUT ANY WARRANTY.  No author or distributor
  34. accepts responsibility to anyone for the consequences of using it
  35. or for whether it serves any particular purpose or works at all,
  36. unless he says so in writing.  Refer to the GNU CC General Public
  37. License for full details.
  38.  
  39. Everyone is granted permission to copy, modify and redistribute
  40. GNU CC, but only under the conditions described in the
  41. GNU CC General Public License.   A copy of this license is
  42. supposed to have been given to you along with GNU CC so you
  43. can know your rights and responsibilities.  It should be in a
  44. file named COPYING.  Among other things, the copyright notice
  45. and this notice must be preserved on all copies.  
  46. */
  47.  
  48. #ifndef ThreadEventPairingHeap_h
  49. #define ThreadEventPairingHeap_h 1
  50.  
  51. #include "ThreadEvent.h"
  52.  
  53. #ifndef ThreadEventPairingHeapIndex
  54. #define ThreadEventPairingHeapIndex unsigned short
  55. #endif
  56.  
  57. #ifndef ThreadEventPairingHeapIndex_NULL
  58. #define ThreadEventPairingHeapIndex_NULL 0xffff
  59. #endif
  60.  
  61. #ifndef _ThreadEvent_typedefs
  62. #define _ThreadEvent_typedefs 1
  63. typedef void (*ThreadEventProcedure)(ThreadEvent );
  64. typedef ThreadEvent  (*ThreadEventMapper)(ThreadEvent );
  65. typedef ThreadEvent  (*ThreadEventCombiner)(ThreadEvent , ThreadEvent );
  66. typedef int  (*ThreadEventPredicate)(ThreadEvent );
  67. typedef int  (*ThreadEventComparator)(ThreadEvent , ThreadEvent );
  68. #endif
  69.  
  70.  
  71. struct ThreadEventPairingHeapRecord 
  72. {
  73.   ThreadEventPairingHeapIndex   sibling;
  74.   ThreadEventPairingHeapIndex   children;
  75.   ThreadEvent                   item;
  76.   char                  valid;
  77. };
  78.  
  79. class ThreadEventPairingHeapTrav;
  80.  
  81. class ThreadEventPairingHeap
  82. {
  83.   friend class          ThreadEventPairingHeapTrav;
  84.  
  85.   ThreadEventPairingHeapRecord* storage;
  86.   int                   elements;
  87.   ThreadEventPairingHeapIndex   allocatedSize;
  88.   ThreadEventPairingHeapIndex   freelist;
  89.   ThreadEventPairingHeapIndex   root;
  90.  
  91.   void                  make_room(int atLeast);
  92.   ThreadEventPairingHeapIndex   get_cell();
  93.   void                  return_cell(ThreadEventPairingHeapIndex cell);
  94.   ThreadEventPairingHeapIndex   make_child(ThreadEventPairingHeapIndex a, 
  95.                                    ThreadEventPairingHeapIndex b);
  96.  
  97. public:
  98.  
  99.     ThreadEventPairingHeap(int initial_cap = 0);
  100.     ~ThreadEventPairingHeap();
  101.  
  102.   ThreadEventPairingHeapIndex   enq(ThreadEvent  item);
  103.  
  104.   ThreadEvent                   deq();
  105.   int                   deq(ThreadEvent& removed);
  106.   ThreadEvent&                  front();
  107.   int                   del_front();
  108.   
  109.   ThreadEvent&                  item(ThreadEventPairingHeapIndex ind);
  110.   int                   valid(ThreadEventPairingHeapIndex ind);
  111.   int                   del(ThreadEventPairingHeapIndex ind);                   
  112.   ThreadEventPairingHeapIndex   front_index();
  113.  
  114.   int                   empty();
  115.   int                   length();
  116.  
  117.   void                  error(const char* msg);
  118. };
  119.  
  120. class ThreadEventPairingHeapTrav
  121. {
  122.   ThreadEventPairingHeap*       h;
  123.   ThreadEventPairingHeapIndex   current;
  124.  
  125.  public:
  126.                         ThreadEventPairingHeapTrav(ThreadEventPairingHeap& heap);
  127.                         ~ThreadEventPairingHeapTrav();
  128.  
  129.   int                   null();
  130.   int                   operator ! ();
  131.   const void*           operator void* ();
  132.  
  133.   ThreadEvent&                  get();
  134.   void                  advance();
  135.   void                  reset();
  136.   void                  reset(ThreadEventPairingHeap& heap);
  137.   void                  del();
  138.   ThreadEventPairingHeapIndex   current_index();
  139. };
  140.  
  141. inline ThreadEventPairingHeap::~ThreadEventPairingHeap()
  142. {
  143.   delete [allocatedSize] storage;
  144. }
  145.  
  146. inline ThreadEventPairingHeapIndex ThreadEventPairingHeap::front_index() 
  147. {
  148.   return root;
  149. }
  150.  
  151. inline int ThreadEventPairingHeap::valid(ThreadEventPairingHeapIndex index) 
  152. {
  153.   return storage[index].valid;
  154. }
  155.  
  156. inline ThreadEvent& ThreadEventPairingHeap::item(ThreadEventPairingHeapIndex i) 
  157. {
  158.   return storage[i].item;
  159. }
  160.  
  161. inline int ThreadEventPairingHeap::empty() 
  162. {
  163.   return (elements <= 0);
  164. }
  165.  
  166. inline int ThreadEventPairingHeap::length() 
  167. {
  168.   return elements;
  169. }
  170.  
  171. inline ThreadEvent ThreadEventPairingHeap::deq()
  172. {
  173.   if (root == ThreadEventPairingHeapIndex_NULL || elements <= 0) 
  174.     error("attempted deq of empty heap");
  175.   ThreadEvent x = storage[root].item; 
  176.   del_front();
  177.   return x;
  178. }
  179.  
  180. inline int ThreadEventPairingHeap::deq(ThreadEvent& x)
  181. {
  182.   if (root == ThreadEventPairingHeapIndex_NULL || elements <= 0) 
  183.     return 0;
  184.   else
  185.   {
  186.     x = storage[root].item; 
  187.     del_front();
  188.     return 1;
  189.   }
  190. }
  191.  
  192. inline ThreadEvent& ThreadEventPairingHeap::front()
  193. {
  194.   if (root == ThreadEventPairingHeapIndex_NULL || elements <= 0) 
  195.     error("attempted front of empty heap");
  196.   return storage[root].item;
  197. }
  198.  
  199.  
  200. inline ThreadEventPairingHeapTrav::~ThreadEventPairingHeapTrav() {}
  201.  
  202. inline int ThreadEventPairingHeapTrav::null()
  203. {
  204.   return current == ThreadEventPairingHeapIndex_NULL;
  205. }
  206.  
  207. inline int ThreadEventPairingHeapTrav::operator !()
  208. {
  209.   return current == ThreadEventPairingHeapIndex_NULL;
  210. }
  211.  
  212. inline const void* ThreadEventPairingHeapTrav::operator void*()
  213. {
  214.   return (current == ThreadEventPairingHeapIndex_NULL)? 0 : this;
  215. }
  216.  
  217. inline ThreadEventPairingHeapIndex ThreadEventPairingHeapTrav::current_index()
  218. {
  219.   return current;
  220. }
  221.  
  222. inline ThreadEvent& ThreadEventPairingHeapTrav::get()
  223. {
  224.   if (current == ThreadEventPairingHeapIndex_NULL)
  225.     h->error("get of null traverser");
  226.   return h->storage[current].item;
  227. }
  228.  
  229. extern void default_ThreadEventPairingHeap_error_handler(char*);
  230. extern one_arg_error_handler_t ThreadEventPairingHeap_error_handler;
  231.  
  232. extern one_arg_error_handler_t 
  233.         set_ThreadEventPairingHeap_error_handler(one_arg_error_handler_t f);
  234.  
  235. #endif
  236. @
  237.